1. Field of the Invention
The present invention relates generally to data processing, and more particularly to a computer implemented method, apparatus, and computer usable program code for detecting and tracking monotonicity for accelerating range queries and inequality queries.
2. Description of the Related Art
Increasing numbers of companies and individuals rely on data retrieval products in order to efficiently access large amounts of data. The data is often stored in a database. In database systems, data is stored in tables. Tables are made up of records, and records are made up of fields or columns. Sometimes two or more columns might be interlinked with one being generated from the other. A column generated from another original or base column is referred to as a generated column.
In database systems, queries are used to retrieve specified data. A query is a request or a specific set of instructions for extracting particular data from a database. Queries are made up of data items or fields to be retrieved and may have limits set on the scope of the data and/or sorting order specified.
To speed up query processing, users and administrators often create indexes. These indexes tend to be on columns in which the queries have predicates or conditions. If the generated column has an index, the index may be used to answer queries which have conditions on the base column. For example, the query may be rewritten to use the generated column. Typically, queries may be rewritten. However, if the query has a range condition or an inequality condition, the query needs to know that the generated column is monotonic before the queries may safely be rewritten. An equality condition for a query predicate is a condition which will result in only one value for that predicate qualifying. For example, the condition “where itemID=10” is an equality condition which will qualify those with itemID=10. A range condition for a query predicate is typically a condition which will result in more than one predicate value for that predicate qualifying. For example, the condition “where itemID between 2 and 4” will result in all values between the boundaries 2 and 4 qualifying. Other examples of range conditions would be “where itemID>2”, “where itemID>=2”, “where itemID<2” or “where itemID<=2”.
Monotonic functions preserve the given order in an increasing or decreasing order. As a result, monotonic functions change in one direction only; thus either strictly rising or strictly falling but not reversing direction. A function F(n) is monotonic if x>y implies F(x)>=F(y) or if x>y then F(x)<=F(y). Examples of monotonic functions include incrementing years. Examples of non-monotonic functions include numeric associates with months January 1, February 2, December 12, and so forth. If the function is not monotonic, then using the index for range or inequality queries could lead to wrong results. Knowing that a function is monotonic is valuable because the function may be used for range and inequalities queries.
The current art on monotonic determination is based on knowledge of identifiable monotonic sub functions being used in the function. If the database system is unable to identify the subfunction as monotonic, the whole function must be flagged as non-monotonic. As a result, the whole function may be monotonic but is flagged as non-monotonic because of the sub-function classification. Thus, the index on the generated column may not be used for conditions with range or inequality queries on the base column, limiting the usage scenarios for the defined index.